package ljl.alg.jianzhioffer.round2;

import commons.Node;

import java.util.ArrayList;
import java.util.List;

/**
 * 把一个二叉搜索树变成双向循环链表
 * */
public class _36_tree_to_list {
    
    /**
     * 我直接遍历一遍然后一个个连起来行吗，试试
     *
     * 出来了，而且还很快
     * 递归的怎么写？
     * */
    public Node treeToDoublyList3(Node root) {
        if (root == null) return null;
        List<Node> list = new ArrayList<>();
        dfs(list, root);
        Node head = list.get(0);
        Node prev = head;
        for (int i = 1; i < list.size(); i++) {
            Node cur = list.get(i);
            cur.left = prev;
            prev.right = cur;
            prev = cur;
        }
        prev.right = head;
        head.left = prev;
        return head;
    }
    void dfs(List<Node> list, Node root) {
        if (root == null) return;
        dfs(list, root.left);
        list.add(root);
        dfs(list, root.right);
    }
    
    /**
     * 试试递归的
     * 得找到头和尾再递归，不然找不到了
     * 就完了
     *
     * 假设它返回头
     *
     * 咋这么慢啊，我是不是写错了？又麻烦，又慢！
     *
     * */
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node leftHead = treeToDoublyList(root.left);
        Node p = leftHead;
        // 如果左节点不是空的就连接左节点和 root
        while (p != null && p.right != leftHead)
            p = p.right;
        if (p != null) {
            p.right = root;
            root.left = p;
        }
        // 如果右节点不是空的就连接 root 和右节点
        Node rightHead = treeToDoublyList(root.right);
        if (rightHead != null) {
            root.right = rightHead;
            rightHead.left = root;
        }
        p = rightHead;
        while (p != null && p.right != rightHead) {
            p = p.right;
        }
        // 处理处理首尾节点，连起来
        if (leftHead == null)
            leftHead = root;
        if (p == null)
            p = root;
        p.right = leftHead;
        leftHead.left = p;
        return leftHead;
    }
    
    /**
     * 路飞的解法值得一个新类
     *
     * 他为什么这么牛逼？为什么？
     *
     * */
    class lufei{
    
        Node pre, head;
        public Node treeToDoublyList(Node root) {
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }
        void dfs(Node root) {
            if (root == null) return;
            dfs(root.left);
            // 他这个角度非常好，从 pre 入手
            if (pre != null) pre.right = root;
            // pre 如果是 null 当前必然是 head 了
            else head = root;
            root.left = pre;
            pre = root;
            dfs(root.right);
        }
    }
}
